package com.ywgt;

import java.util.Arrays;

/**
 * 弗洛伊德算法（求取最短路径，为地图中的每个点）
 */
public class Floyd {
    static final int N=1000;//表示两点间不连通
    public static void main(String[] args) {
        char[] points={'A','B','C','D','E','F','G'};
        int [][] diatance=new int[points.length][points.length];
        diatance[0]=new int[]{0,5,7,N,N,N,2};
        diatance[1]=new int[]{5,0,N,9,N,N,3};
        diatance[2]=new int[]{7,N,0,N,8,N,N};
        diatance[3]=new int[]{N,9,N,0,N,4,N};
        diatance[4]=new int[]{N,N,8,N,0,5,4};
        diatance[5]=new int[]{N,N,N,4,5,0,6};
        diatance[6]=new int[]{2,3,N,N,4,6,0};
        Graph graph = new Graph(points.length, diatance, points);
        graph.minTree();
        graph.show();
    }
}
class Graph{
    //各个结点的数组
    char [] point;
    //各个结点之间的距离（最终求最短）
    int [][] distance;
    //前驱结点，到达此点的上一个结点
    int [][] lastPoint;

    public Graph(int length,int[][] distance,char[] point) {
        this.distance=distance;
        this.point=point;
        lastPoint=new int[point.length][point.length];
        for (int i = 0; i < lastPoint.length; i++) {
            Arrays.fill(lastPoint[i],i);
        }

    }

    /**
     * 为全部的结点生成最短路径
     */
    public void minTree(){
        for (int i = 0; i < point.length; i++) { //当前遍历的就是中间点
            for (int j = 0; j < point.length; j++) { //相当于起点
                for (int k = 0; k < point.length; k++) { //终点
                    if(distance[i][j]+distance[i][k]<distance[j][k]){ //中间点到起点+中间点到终点的距离小于起点到终点的和
                        // （和两点间直线最短无关，起点终点中间可能存在很多店）
                        distance[j][k]=distance[i][j]+distance[i][k]; //将起点终点之间的距离换成最小值
                        lastPoint[j][k]=lastPoint[i][k]; //将之前的路ik断了 从中间点i指向终点K（相当于一条路径，一直在变化）
                    }
                }
            }
        }
    }


    public void show(){
        for (int[] ints : distance) {
            for (int anInt : ints) {
                System.out.print(anInt+"\t");
            }
            System.out.println();
        }

        for (int i = 0; i < lastPoint.length; i++) {
            for (int j = 0; j < lastPoint[i].length; j++) {
                System.out.print("\t"+point[lastPoint[i][j]]+"\t");
            }
            System.out.println();
        }
    }
}
